翻訳と辞書 Words near each other ・ Erechthias ・ Erechthias ascensionae ・ Erechthias chionodira ・ Erechthias darwini ・ Erechthias diaphora ・ Erechthias dracaenura ・ Erechthias flavistriata ・ Erechthias glyphidaula ・ Erechthias grayi ・ Erechthias kerri ・ Erechthias lychnopa ・ Erechthias minuscula ・ Erechthias molynta ・ Erechthias mystacinella ・ Erdős–Kac theorem ・ Erdős–Ko–Rado theorem ・ Erdős–Mordell inequality ・ Erdős–Nagy theorem ・ Erdős–Nicolas number ・ Erdős–Pósa theorem ・ Erdős–Rado theorem ・ Erdős–Rényi model ・ Erdős–Stone theorem ・ Erdős–Straus conjecture ・ Erdős–Szekeres theorem ・ Erdős–Szemerédi theorem ・ Erdős–Turán conjecture on additive bases ・ Erdős–Turán inequality ・ Erdős–Woods number ・ Erdőtarcsa Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Erdős–Ko–Rado theorem ： ウィキペディア英語版 Erdős–Ko–Rado theorem In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem on intersecting set families. It is part of the theory of hypergraphs, specifically, uniform hypergraphs of rank ''r''. The theorem is as follows. If $n\backslash geq2r$ and $A$ is a family of distinct subsets of $\backslash$ such that each subset is of size $r$ and each pair of subsets intersects, then the maximum number of sets that can be in $A$ is given by the binomial coefficient :$\backslash binom.$ (Since a family of sets may be called a hypergraph, and since every set in $A$ has size ''r'', $A$ is a uniform hypergraph of rank ''r''.) According to the theorem was proved in 1938, but was not published until 1961 in an apparently more general form. The subsets in question were only required to be size ''at most'' $r$, and with the additional requirement that no subset be contained in any other. This statement is not actually more general: any subset that has size less than $r$ can be increased to size $r$ to make the above statement apply. ==Proof== The original proof of 1961 used induction on ''n''. In 1972, Gyula O. H. Katona gave the following short proof using double counting. Suppose we have some such family of subsets ''A''. Arrange the elements of in any cyclic order, and consider the sets from ''A'' that form intervals of length ''r'' within this cyclic order. For example if ''n'' = 8 and ''r'' = 3, we could arrange the numbers into the cyclic order (3,1,5,4,2,7,6,8), which has eight intervals: :(3,1,5), (1,5,4), (5,4,2), (4,2,7), (2,7,6), (7,6,8), (6,8,3), and (8,3,1). However, it is not possible for all of the intervals of the cyclic order to belong to ''A'', because some pairs of them are disjoint. Katona's key observation is that at most ''r'' of the intervals for a single cyclic order may belong to ''A''. To see this, note that if (''a''1, ''a''2, ..., ''a''''r'') is one of these intervals in ''A'', then every other interval of the same cyclic order that belongs to ''A'' separates ''ai'' and ''a''''i'' + 1 for some ''i'' (that is, it contains precisely one of these two elements). The two intervals that separate these elements are disjoint, so at most one of them can belong to ''A''. Thus, the number of intervals in ''A'' is one plus the number of separated pairs, which is at most ''(r-1)''. Based on this idea, we may count the number of pairs (''S'',''C''), where ''S'' is a set in ''A'' and ''C'' is a cyclic order for which ''S'' is an interval, in two ways. First, for each set ''S'' one may generate ''C'' by choosing one of ''r''! permutations of ''S'' and (''n'' − ''r'')! permutations of the remaining elements, showing that the number of pairs is |''A''|''r''!(''n'' − ''r'')!. And second, there are (''n'' − 1)! cyclic orders, each of which has at most ''r'' intervals of ''A'', so the number of pairs is at most r(''n'' − 1)!. Combining these two counts gives the inequality :$|A|r!(n-r)!\backslash le\; r(n-1)!$ and dividing both sides by ''r''!(''n'' − ''r'')! gives the result :$|A|\backslash le\; \backslash frac=.$ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Erdős–Ko–Rado theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.